/*
 * @lc app=leetcode.cn id=1175 lang=typescript
 *
 * [1175] 质数排列
 */

// @lc code=start
function numPrimeArrangements(n: number): number {
  const mod = 1e9 + 7;
  // 试除法求质数个数
  const isPrime = (n: number): boolean => {
    if (n <= 1) return false;
    for (let i = 2; i * i <= n; i++) {
      if (n % i === 0) return false;
    }
    return true;
  };

  let primes = 0;
  for (let i = 2; i <= n; i++) {
    if (isPrime(i)) primes++;
  }

  let ans = 1;
  let nPrimes = n - primes;
  // 素数的排列方案数
  while (primes > 0) {
    ans %= mod;
    ans *= primes--;
  }
  // 非素数的排列方案数
  while (nPrimes > 0) {
    ans %= mod;
    ans *= nPrimes--;
  }
  return ans;
}
// @lc code=end
